package lc.q1_50;

/**
 * 给定一个非负整数数组，你最初位于数组的第一个位置。
 *
 * 数组中的每个元素代表你在该位置可以跳跃的最大长度。
 *
 * 你的目标是使用最少的跳跃次数到达数组的最后一个位置。
 *
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode-cn.com/problems/jump-game-ii
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 */
public class Q45 {
    /**
     * 采取贪心算法，下次能跳跃的格子中寻找下下次能跳跃到最远的那一个
     * @param nums
     * @return
     */
    public int jump(int[] nums) {
        int k = 0;
        for (int i = 0; i < nums.length-1; ) {
            int num = nums[i];
            if (i + num >= nums.length -1) {
                // 此时表示跳完了
                return k + 1;
            }
            int max = 0;
            int l = 0;
            for (int j = i+1; j <= i + num && j < nums.length; j++) {
                if (nums[j]+j >= max) {
                    max = nums[j] + j;
                    l = j;
                }
            }
            i = l;
            k ++;
        }
        return k;
    }
}
